package Hard;

import java.util.*;

public class JobAssignment {
    public static void main(String[] args) {
        int[] jobs = { 1, 2, 4, 7, 8 };
        System.out.println(minimumTimeRequired(jobs, 2));
        System.out.println(SolutionByDFS.minimumTimeRequired(jobs, 2));
    }

    // static关键字：方便在没有创建对象的情况下来进行调用，被static关键字修饰的不需要创建对象去调用，直接根据类名就可以去访问
    // https://baijiahao.baidu.com/s?id=1636927461989417537&wfr=spider&for=pc

    /**
     * 给你一个整数数组 jobs ，其中 jobs[i] 是完成第 i 项工作要花费的时间
     * 
     * 请你将这些工作分配给 k 位工人。所有工作都应该分配给工人，且每项工作只能分配给一位工人
     * 
     * 工人的 工作时间 是完成分配给他们的所有工作花费时间的总和
     * 
     * 请你设计一套最佳的工作分配方案，使工人的 最大工作时间 得以 最小化
     * 
     * 返回分配方案中尽可能 最小 的 最大工作时间
     * 
     * 1 <= k <= jobs.length <= 12, 1 <= jobs[i] <= 10^7
     * 
     * @param jobs
     * @param k
     * @return
     */
    public static int minimumTimeRequired(int[] jobs, int k) { // 二分 + 回溯 + 减枝
        Arrays.sort(jobs);
        int low = 0, high = jobs.length - 1;
        while (low < high) {
            int temp = jobs[low];
            jobs[low] = jobs[high];
            jobs[high] = temp;
            low++;
            high--;
        }
        int l = jobs[0], r = Arrays.stream(jobs).sum();
        while (l < r) {
            int mid = (l + r) >> 1;
            if (check(jobs, k, mid)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }

    public static boolean check(int[] jobs, int k, int limit) {
        int[] workloads = new int[k];
        return backtrack(jobs, workloads, 0, limit);
    }

    public static boolean backtrack(int[] jobs, int[] workloads, int i, int limit) {
        if (i >= jobs.length) {
            return true;
        }
        int cur = jobs[i];
        for (int j = 0; j < workloads.length; ++j) {
            if (workloads[j] + cur <= limit) {
                workloads[j] += cur;
                if (backtrack(jobs, workloads, i + 1, limit)) {
                    return true;
                }
                workloads[j] -= cur;
            }
            // 如果当前工人未被分配工作，那么下一个工人也必然未被分配工作
            // 或者当前工作恰能使该工人的工作量达到了上限
            // 这两种情况下我们无需尝试继续分配工作
            if (workloads[j] == 0 || workloads[j] + cur == limit) {
                break;
            }
        }
        return false;
    }

    class SolutionByDP {
        public int minimumTimeRequired(int[] jobs, int k) { // 动态规划 + 转状态压缩
            int n = jobs.length;
            int[] sum = new int[1 << n];
            for (int i = 1; i < (1 << n); i++) {
                int x = Integer.numberOfTrailingZeros(i), y = i - (1 << x);
                sum[i] = sum[y] + jobs[x];
            }

            int[][] dp = new int[k][1 << n];
            for (int i = 0; i < (1 << n); i++) {
                dp[0][i] = sum[i];
            }

            for (int i = 1; i < k; i++) {
                for (int j = 0; j < (1 << n); j++) {
                    int minn = Integer.MAX_VALUE;
                    for (int x = j; x != 0; x = (x - 1) & j) {
                        minn = Math.min(minn, Math.max(dp[i - 1][j - x], sum[x]));
                    }
                    dp[i][j] = minn;
                }
            }
            return dp[k - 1][(1 << n) - 1];
        }
    }

    static class SolutionByDFS {
        static int[] jobs;
        static int n, k;
        static int ans = 0x3f3f3f3f;

        public static int minimumTimeRequired(int[] _jobs, int _k) {
            jobs = _jobs;
            n = jobs.length;
            k = _k;
            int[] sum = new int[k];
            dfs(0, 0, sum, 0);
            return ans;
        }

        /**
         * 【补充说明】不理解可以看看下面的「我猜你问」的 Q5 哦 ~
         * 
         * u : 当前处理到那个 job used : 当前分配给了多少个工人了 sum : 工人的分配情况 例如：sum[0] = x 代表 0 号工人工作量为
         * x max : 当前的「最大工作时间」
         */
        static void dfs(int u, int used, int[] sum, int max) {
            if (max >= ans)
                return;
            if (u == n) {
                ans = max;
                return;
            }
            // 优先分配给「空闲工人」
            if (used < k) {
                sum[used] = jobs[u];
                dfs(u + 1, used + 1, sum, Math.max(sum[used], max));
                sum[used] = 0;
            }
            for (int i = 0; i < used; i++) {
                sum[i] += jobs[u];
                dfs(u + 1, used, sum, Math.max(sum[i], max));
                sum[i] -= jobs[u];
            }
        }
    }
}